package 开始的算法算法入门8月.动态规划;
// https://leetcode-cn.com/problems/climbing-stairs/
public class 爬楼梯700823 {
    class Solution {
        //和斐波那契数列差不多
        //动态规划思路： 要考虑第爬到第n阶楼梯时候可能是一步，也可能是两步。
        // 1.计算爬上n-1阶楼梯的方法数量。因为再爬1阶就到第n阶
        // 2.计算爬上n-2阶楼梯体方法数量。因为再爬2阶就到第n阶 那么f(n)=f(n-1)+f(n-2);
//为什么不是f(n)=f(n-1)+1+f(n-2)+2呢，因为f(n)是爬楼梯方法数量，不是爬到n阶楼梯的步数
        public int climbStairs(int n) {
            int[] res = new int[n];
            res[0] = 1;
            if (n == 1) {
                return 1;
            } else {
                res[1] = 2;
                if (n > 2) {
                    for (int i = 2; i < n; i++) {
                        res[i] = res[i - 1] + res[i - 2];
                    }
                }
            }
            return res[n - 1];
        }
    }
}
